package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 322. 零钱兑换
 * 剑指 Offer II 103. 最少的硬币数目
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/20 17:04
 */
public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int length = coins.length;
        int[] cc = new int[length];
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < length; j++) {
                if (i - coins[j] >= 0) {
                    cc[j] = dp[i - coins[j]];
                } else {
                    cc[j] = -1;
                }
            }
            dp[i] = Integer.MAX_VALUE;
            for (int c : cc) {
                if (c > -1) {
                    dp[i] = Math.min(dp[i], c + 1);
                }
            }
            dp[i] = dp[i] != Integer.MAX_VALUE ? dp[i] : -1;
        }
        return dp[amount];
    }
}
